package org.example.algorithms;

public class Mining {
    private static int[][] dp;
    private static String[][] mines;


    public static void maxValue(int[] values, int[] labors, int max) {
        if (values == null || values.length == 0) return;
        if (labors == null || labors.length == 0) return;
        if (values.length != labors.length || max <= 0) return;

        dp = new int[values.length + 1][max + 1];
        mines = new String[values.length+1][max+1];
        String mine;
        for (int i = 1; i <= labors.length; i++) {
            for (int j = 1; j <= max; j++) {
                // 选择的金矿所需人力超过最大
                if (j < labors[i-1]) {
                    dp[i][j] = dp[i-1][j];
                    mines[i][j] = getMine(i-1, j);
                }
                else {
                    if (dp[i-1][j] >= values[i-1]+dp[i-1][j-labors[i-1]]) {
                        dp[i][j] = dp[i-1][j];
//                        if (mines[i-1][j] == null) {
//                            mine = String.valueOf(i - 1);
//                        } else {
//                            mine = mines[i-1][j];
//                        }
                        mines[i][j] = getMine(i, j) + ", " + getMine(i-1, j);
                    }
                    if (values[i-1]+dp[i-1][j-labors[i-1]] > dp[i-1][j]) {
                        dp[i][j] = values[i-1]+dp[i-1][j-labors[i-1]];

//                        if (mines[i-1][j-labors[i-1]] == null) {
//                            mine = String.valueOf(i - 1);
//                        } else {
//                            mine =mines[i-1][j-labors[i-1]];
//                        }
                        mines[i][j] = getMine(i, j) +  ", " + getMine(i-1, j-labors[i-1]);
                    }
                }

            }
        }
    }

    protected static String getMine(int x, int y) {
        String m = "";
        if (mines[x][y] == null) {
            if  (x != 0 || y != 0) {
                m = String.valueOf(x - 1);
            } else {
                m = "";
            }
        } else {
            m =mines[x][y];
        }

//        System.out.println(m);
        return m;
    }

    public static void main(String[] args) {
        // 金矿储量
        int[] values = {6,3,5,4,6};
        // 开采需要人力
        int[] labors = {2,2,6,5,4};
        int max = 10;
        maxValue(values, labors, max);

        // 打印要选取的金矿
        System.out.println("============ result ");
        int tMax = dp[1][1];
        int tMaxX = 1;
        int tMaxY = 1;
        for (int i = 1; i <= labors.length  ; i++) {
            for (int j = 1; j <= max; j++) {
//                System.out.println(">>>dp[" + i + "][" + j + "]" + dp[i][j]);
                if (dp[i][j] > tMax) {
                    tMax = dp[i][j];
                    tMaxX = i;
                    tMaxY = j;
                }
            }
        }
        System.out.println("最大金矿：" + dp[tMaxX][tMaxY]);
        System.out.println("选择的金矿序号: " + mines[tMaxX][tMaxY]);
    }
}
